#pragma once
#include "TypeDefin.h"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 

示例 1：


输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：


输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
// 方法1 递归方法 不带头结点
//出口 head==null
// 1 2 3 4
ListNode* reverseList(ListNode* head) {
    //刚开始没加这个 head->next== nullptr
    if (head== nullptr || head->next== nullptr)
        return head;

    ListNode* listEnd= reverseList(head->next);//返回4


    head->next->next=head;

    head->next= nullptr;

    return listEnd;

}


//非递归方式 建立一个节点
//1 2 3 4
ListNode* reverseList(ListNode* head) {

     ListNode* ht=new ListNode();
     ht->next=head;
    while (head)
    {
       ListNode* temp=head;
       head=head->next;
       //重点利用头差法
       temp->next=ht->next;
       ht->next=temp;
    }

    return ht->next;
}


//非递归方式不建立头节点
//1 2 3 4
ListNode* reverseList(ListNode* node) {
    if (node == nullptr || node->next == nullptr)
        return node;
    //头插发 没有头结点的头插法
    //https://zhuanlan.zhihu.com/p/488188589
    ListNode *nextNextNode = node;//
    ListNode *end = node->next;
    // 1 2 3 4 4
    while (end != nullptr) {
        //1-3
        nextNextNode = end->next;//保留下一个指针
        end->next = node;//2-1
        node = end;// node永远指向第一个节点
        end = nextNextNode; //3
    }

    return node;
}